package com.wujian.love.study.sufa;

/**
 * @ClassName: Demo1
 * @Description: 304. 二维区域和检索 - 矩阵不可变
 * 给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
 * @Author: wuj
 * @Date: 2021-03-02 16:50
 * 实例:
 * 给定 matrix = [
 * [3, 0, 1, 4, 2],
 * [5, 6, 3, 2, 1],
 * [1, 2, 0, 1, 5],
 * [4, 1, 0, 1, 7],
 * [1, 0, 3, 0, 5]
 * ]
 * <p>
 * sumRegion(2, 1, 4, 3) -> 8
 * sumRegion(1, 1, 2, 2) -> 11
 * sumRegion(1, 2, 2, 4) -> 12
 * <p>
 **/
class NumMatrix {

        int[][] sums ;


    public NumMatrix(int[][] matrix) {
        //初始化的时候进行前缀的计算
        int length = matrix.length;
        if(length > 0){
            int n = matrix[0].length;
            sums = new int[length][n+1];
            for (int i = 0;i<length;i++){
                for (int j=0;j<0;j++){
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
}

